#include <iostream>

using namespace std;

class Solution {
public:
	
    double myPow(double x, int n) {
		if(n == 0) return 1.0;
		
        double a = back2(x, abs(n));
		if(n < 0){
			return 1/a;
		}
		return a;
    }
	// 最笨的递归会导致内存溢出
	double back(double x, int n){
		if(n==1){
            return x;
        }
        return x * back(x, n-1);
	}
	
	double back2(double x, long n){ // 这里的long类型防止溢出
		if(n == 1) return x;
		double y = back2(x, n/2); // 这一步非常关键，先算出来，否则会超时
		if(n%2== 1){
			return x * y * y;
		}else{
			return y * y;
		}
		
	}
};

int main(){
	Solution so;
	double a = so.myPow(2, 10);
	cout << a << endl;
	return 0;
}